<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="SvFVi" id="SvFVi"><span data-lake-id="uf1e450c7" id="uf1e450c7">典型回答</span></h1>
  <h2 data-lake-id="ZFDVU" id="ZFDVU"><span data-lake-id="ucb31cf71" id="ucb31cf71">为什么不继续使用链表</span></h2>
  <p data-lake-id="u241a0825" id="u241a0825"><span data-lake-id="uca41cf59" id="uca41cf59">我们知道，HashMap解决hash冲突是通过拉链法完成的，在JDK8之前，如果产生冲突，就会把新增的元素增加到当前桶所在的链表中。</span></p>
  <p data-lake-id="u6835cad8" id="u6835cad8"><span data-lake-id="ua18e7144" id="ua18e7144">这样就会产生一个问题，当某个bucket冲突过多的时候，其指向的链表就会变得很长，这样如果put或者get该bucket上的元素时，复杂度就无限接近于O(N)，这样显然是不可以接受的。</span></p>
  <p data-lake-id="uf873276d" id="uf873276d"><span data-lake-id="u3ca1eb9c" id="u3ca1eb9c">所以在JDK1.7的时候，在元素put之前做hash的时候，就会充分利用扰动函数，将不同KEY的hash尽可能的分散开。不过这样做起来效果还不是太好，所以当链表过长的时候，我们就要对其数据结构进行修改</span></p>
  <h2 data-lake-id="Bt537" id="Bt537"><span data-lake-id="u4b72136c" id="u4b72136c">为什么是红黑树</span></h2>
  <p data-lake-id="u7f995b10" id="u7f995b10"><span data-lake-id="ud9b6a32f" id="ud9b6a32f">当元素过多的时候，用什么来代替链表呢？我们很自然的就能想到可以用二叉树查找树代替，所谓的二叉查找树，一定是left &lt; root &lt; right，这样我们遍历的时间复杂度就会由链表的O(N)变为二叉查找树的O(logN)，二叉查找树如下所示：</span></p>
  <p data-lake-id="u17639dbe" id="u17639dbe"><img src="https://cdn.nlark.com/yuque/0/2022/png/719664/1668933021439-3f3fcfbf-16cd-4f3f-9047-a21c856596d7.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_23%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ue239325f" id="ue239325f"><span data-lake-id="udb4f610e" id="udb4f610e">但是，对于极端情况，当子节点都比父节点大或者小的时候，二叉查找树又会退化成链表，查询复杂度会重新变为O(N)，如下所示：</span></p>
  <p data-lake-id="u7329e150" id="u7329e150"><img src="https://cdn.nlark.com/yuque/0/2022/png/719664/1668933119478-0745c9b5-270f-4f81-8282-2905667a69bc.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_16%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ua1640224" id="ua1640224"><span data-lake-id="u88cf5f05" id="u88cf5f05">所以，我们就需要二叉平衡树出场，他会在每次插入操作时来检查</span><strong><span data-lake-id="ubad2dc9b" id="ubad2dc9b">每个节点的左子树和右子树的高度差至多等于1</span></strong><span data-lake-id="ua5421a2b" id="ua5421a2b" class="lake-fontsize-12" style="color: rgb(0, 0, 0)">，如果&gt;1，就需要进行左旋或者右旋操作，使其查询复杂度一直维持在O(logN)。</span></p>
  <p data-lake-id="u81fce621" id="u81fce621"><span data-lake-id="ue1fe1c30" id="ue1fe1c30" class="lake-fontsize-12" style="color: rgb(0, 0, 0)">但是这样就万无一失了吗？其实并不然，我们不仅要保证查询的时间复杂度，还需要保证插入的时间复杂度足够低，因为平衡二叉树要求高度差最多为1，非常严格，导致每次插入都需要左旋或者右旋，极大的消耗了插入的时间。</span></p>
  <p data-lake-id="ud7477946" id="ud7477946"><img src="https://cdn.nlark.com/yuque/0/2022/png/719664/1668933432032-4d1e27a8-2a09-48f6-a773-ff8f332c6deb.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_36%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u288adeb7" id="u288adeb7"><span data-lake-id="uef8b196d" id="uef8b196d">对于那些插入和删除比较频繁的场景，AVL树显然是不合适的。为了保证查询和插入的时间复杂度维持在一个均衡的水平上，所以就引入了红黑树。</span></p>
  <p data-lake-id="ufc14bca3" id="ufc14bca3"><span data-lake-id="u65f23961" id="u65f23961">在红黑树中，所有的叶子节点都是黑色的的空节点，也就是叶子节点不存数据；任何相邻的节点都不能同时为红色，红色节点是被黑色节点隔开的，每个节点，从该节点到达其可达的叶子节点的所有路径，都包含相同数目的黑色节点。</span></p>
  <p data-lake-id="ufb161e81" id="ufb161e81"><span data-lake-id="ucefae11f" id="ucefae11f">我们可以得到如下结论：红黑树不会像AVL树一样追求绝对的平衡，它的插入最多两次旋转，删除最多三次旋转，在频繁的插入和删除场景中，红黑树的时间复杂度，是优于AVL树的。</span></p>
  <p data-lake-id="ud94239c6" id="ud94239c6"><img src="https://cdn.nlark.com/yuque/0/2022/png/719664/1668933538551-584d0077-4d4a-4261-b1f4-f9d25685c680.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_34%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u49d337ca" id="u49d337ca"><span data-lake-id="u0c5655c9" id="u0c5655c9">综上所述，这就是HashMap选择红黑树的原因。</span></p>
  <h1 data-lake-id="k7wUX" id="k7wUX"><span data-lake-id="u07efe5ed" id="u07efe5ed">知识扩展</span></h1>
  <h2 data-lake-id="pHVMn" id="pHVMn"><span data-lake-id="u44985e1f" id="u44985e1f">为什么是链表长度达到8的时候转</span></h2>
  <p data-lake-id="u80f07e18" id="u80f07e18"><span data-lake-id="ub46558b1" id="ub46558b1">这个问题有两层含义，第一个是为什么不在冲突的时候立刻转为红黑树，第二个是为什么是达到8的时候转</span></p>
  <h3 data-lake-id="k1iHl" id="k1iHl"><span data-lake-id="udaf8a1b7" id="udaf8a1b7">为什么不在冲突的时候立刻转</span></h3>
  <p data-lake-id="u3f330356" id="u3f330356"><span data-lake-id="uacbce79e" id="uacbce79e">原因有2，从空间维度来讲，因为红黑树的空间是普通链表节点空间的2倍，立刻转为红黑树后，太浪费空间；从时间维度上讲，红黑树虽然查询比链表快，但是插入比链表慢多了，每次插入都要旋转和变色，如果小于8就转为红黑树，时间和空间的综合平衡上就没有链表好</span></p>
  <h3 data-lake-id="Kjb3v" id="Kjb3v"><span data-lake-id="u42f9b3df" id="u42f9b3df">为什么长度为8的时候转</span></h3>
  <p data-lake-id="u95b17eb3" id="u95b17eb3"><span data-lake-id="u0fbcc71c" id="u0fbcc71c">先来看源码的一段注释：</span></p>
  <pre lang="java"><code>
/* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins.  In
* usages with well-distributed user hashCodes, tree bins are
* rarely used.  Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006
* more: less than 1 in ten million
 */
</code></pre>
  <p data-lake-id="ua1b23b40" id="ua1b23b40" style="text-align: justify"><span data-lake-id="u931e2769" id="u931e2769">​</span><br></p>
  <p data-lake-id="u54e4ead4" id="u54e4ead4" style="text-align: justify"><span data-lake-id="u04935e1c" id="u04935e1c">大概的翻译就是TreeNode占用的内存是Node的两倍，只有在node数量达到8时才会使用它，而当 node 数量变小时（删除或者扩容），又会变回普通的 Node 。当 hashCode遵循泊松分布时，因为哈希冲突造成桶的链表长度等于8的概率只有0.00000006 。官方认为这个概率足够的低，所以指定链表长度为 8 时转化为红黑树。所以 8 这个数是经过数学推理的，不是瞎写的。</span></p>
  <p data-lake-id="ue83e5d1d" id="ue83e5d1d" style="text-align: justify"><span data-lake-id="u155a9235" id="u155a9235" class="lake-fontsize-12" style="color: rgb(85, 85, 85)">​</span><br></p>
  <h3 data-lake-id="hYk23" id="hYk23"><span data-lake-id="u97ec5302" id="u97ec5302">为什么长度为6的时候转回来？</span></h3>
  <p data-lake-id="u725dd9af" id="u725dd9af"><br></p>
  <p data-lake-id="ub648bbf8" id="ub648bbf8"><span data-lake-id="ufa314744" id="ufa314744">但是，当红黑树节点数小于 6 时，又会把红黑树转换回链表，</span><strong><span data-lake-id="uf2e35762" id="uf2e35762">这个设计的主要原因是出于对于性能和空间的考虑</span></strong><span data-lake-id="uce63b8fb" id="uce63b8fb">。前面讲过为什么直接用红黑树，那同理，转成红黑树之后总要在适当的时机转回来，要不然无论是空间占用大，而且插入性能都会下降。</span></p>
  <p data-lake-id="uddf78293" id="uddf78293"><span data-lake-id="u1baea315" id="u1baea315">​</span><br></p>
  <p data-lake-id="u2a6aa9de" id="u2a6aa9de"><span data-lake-id="u3b2513a9" id="u3b2513a9">8的时候转成红黑树，那么如果小于8立刻转回去，那么就可能会导致频繁转换，所以要选一个小于8的值，但是又不能是7。而通过前面提到的泊松分布可以看到，当红黑树节点数小于 6 时，它所带来的优势其实就是已经没有那么大了，就不足以抵消由于红黑树维护节点所带来的额外开销，此时转换回链表能够节省空间和时间。</span></p>
  <p data-lake-id="uccdb146b" id="uccdb146b"><br></p>
  <p data-lake-id="u515cc5e0" id="u515cc5e0"><span data-lake-id="u3d3845ac" id="u3d3845ac">但是不管怎样，6 这个数值是通过大量实验得到的经验值，在绝大多数情况下取得比较好的效果。</span></p>
  <h2 data-lake-id="SgP5e" id="SgP5e"><span data-lake-id="u58f1182d" id="u58f1182d">双向链表是怎么回事</span></h2>
  <p data-lake-id="u401ef2c4" id="u401ef2c4"><span data-lake-id="u6656e5d7" id="u6656e5d7">HashMap红黑树的数据结构中，不仅有常见的parent，left，right节点，还有一个next和prev节点。这很明显的说明，其不仅是一个红黑树，还是一个双向链表，为什么是这样呢？</span></p>
  <p data-lake-id="uc7dd72bd" id="uc7dd72bd"><span data-lake-id="u4daa9d4c" id="u4daa9d4c">这个其实我们也在之前红黑树退化成链表的时候稍微提到过，红黑树会记录树化之前的链表结构，这样当红黑树退化成链表的时候，就可以直接按照链表重新链接的方式进行（详细分析可以见前面扩容的文章）</span></p>
  <p data-lake-id="ua1b5eb16" id="ua1b5eb16"><span data-lake-id="uc5bc1067" id="uc5bc1067">不过可能有人会问，那不是需要一个next节点就行了，为什么还要prev节点呢？这是因为当删除红黑树中的某个节点的时候，这个节点可能就是原始链表的中间节点，如果把该节点删除，只有next属性是没办法将原始的链表重新链接的，所以就需要prev节点，找到上一个节点，重新成链</span></p>
  <h2 data-lake-id="S2MFB" id="S2MFB"><span data-lake-id="u49f9768b" id="u49f9768b">HashMap的元素没有比较能力，红黑树为什么可以比较？</span></h2>
  <p data-lake-id="u6dbb62ef" id="u6dbb62ef"><span data-lake-id="u5e4452f1" id="u5e4452f1">这里红黑树使用了一个骚操作：</span></p>
  <ol list="ufc939dc7">
   <li fid="u3209fea8" data-lake-id="u015e1fed" id="u015e1fed"><span data-lake-id="udd5e0668" id="udd5e0668">如果元素实现了comparable接口，则直接比较，否则</span></li>
   <li fid="u3209fea8" data-lake-id="u3776c9e8" id="u3776c9e8"><span data-lake-id="u8c543cc9" id="u8c543cc9">则使用默认的仲裁方法，该方法的源码如下：</span></li>
  </ol>
  <pre lang="java"><code>
static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) &lt;= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}
</code></pre>
  <p data-lake-id="u9d24e5d1" id="u9d24e5d1"><br></p>
  <p data-lake-id="uc1dd7aea" id="uc1dd7aea"><br></p>
  <p data-lake-id="u853b003b" id="u853b003b"><br></p>
  <p data-lake-id="u6c4f3f1b" id="u6c4f3f1b"><br></p>
 </body>
</html>